# Brian Kernighan 算法
# 对于任意整数 x，令 x=x~\&~(x-1)x=x & (x−1)，
# 该运算将 xx 的二进制表示的最后一个 11 变成 00。
# 因此，对 xx 重复该操作，直到 xx 变成 00，则操作次数即为 x 的「一比特数」

def countBits(n):
    def countOnes(x):
        ones = 0
        while x > 0:
            x &= (x - 1)
            ones += 1
        return ones

    return [countOnes(i) for i in range(n + 1)]


print(countBits(2))  # [0,0,1]
print(countBits(5))  # [0,1,1,2,1,2]
